package com.xzz.redblacktree;


/**
 * @author: hhz
 * @createDate: 2021-4-23
 */
public class MyRedBlackTree {
    static class Node {
        int value;
        boolean red = true;
        Node parent;
        Node left;
        Node right;

        Node() {
            this.left = this.right = this.parent = null;
        }

        Node(int num) {
            this.value = num;
            this.left = this.right = this.parent = null;
        }
    }

    private Node addNode(Node root, Node newNode) {
        //往根节点下面添加新节点
        System.out.printf("开始连接新节点Node(value=%s)%n", newNode.value);
        //插入情景1：红黑树为空树
        if (null == root) {
            root = newNode;
            root.red = false;
            return root;
        }
        Node currentNode = findNodeForAdd(root, newNode);
        // 插入情景2：插入结点的Key已存在
        if (currentNode.value == newNode.value) {
            if (currentNode.parent == null) {
                return root;
            }
            currentNode = currentNode.parent;
        }
        linkNode(currentNode, newNode);
        return root;

    }

    private Node findNodeForAdd(Node currentNode, Node newNode) {
        if (currentNode.value == newNode.value) {
            return currentNode;
        } else if (currentNode.value > newNode.value) {
            return currentNode.left == null ? currentNode : findNodeForAdd(currentNode.left, newNode);
        } else {
            return currentNode.right == null ? currentNode : findNodeForAdd(currentNode.right, newNode);
        }
    }

    private void linkNode(Node currentNode, Node newNode) {
        // 在current节点下，连接新的insert节点，并完成自平衡操作
        boolean addLeft = false;
        //判断连接到左右字节点
        if (currentNode.value > newNode.value) {
            currentNode.left = newNode;
            addLeft = true;
            System.out.println(currentNode.value + ".left=" + newNode.value);
        } else {
            currentNode.right = newNode;
            addLeft = false;
            System.out.println(currentNode.value + ".right=" + newNode.value);
        }
        newNode.parent = currentNode;
        //插入情景3：插入结点的父结点为黑结点
        if (!currentNode.red) {
            System.out.println("插入情景3：插入结点的父结点为黑结点");
            return;
        }
        //插入情景4：插入结点的父结点为红结点
        System.out.println("/插入情景4：插入结点的父结点为红结点");
        Node parentNode = currentNode.parent;
        boolean currentIsLeft = (parentNode.left != null && parentNode.value == currentNode.value);
        Node currentBrother = currentIsLeft ? parentNode.right : parentNode.left;
        //插入情景4.1：叔叔结点存在并且为红结点
        if (null != currentBrother && currentBrother.red) {
            System.out.println("插入情景4.1：叔叔结点存在并且为红结点");
            //变色
            currentNode.red = false;
            currentBrother.red = false;
            if (parentNode.parent == null) {
                //parent为根节点为黑色，无需再做任何处理
                return;
            }
            parentNode.red = true;
            //把parent当作新的插入结点，继续做插入操作自平衡处理，直到平衡为止
            linkNode(parentNode.parent, parentNode);
            return;
        }
        //插入情景4.2：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的左子结点
        if (currentIsLeft) {
            System.out.println("插入情景4.2：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的左子结点");
            //# 插入情景4.2.1：插入结点是其父结点的左子结点
            if (addLeft) {
                System.out.println("插入情景4.2.1：插入结点是其父结点的左子结点");
                //变色
                currentNode.red = false;
                parentNode.red = true;
                //对parent进行右旋，使得current为parent的父节点
                rightRotation(currentNode, parentNode);
                return;
            }
            //插入情景4.2.2：插入结点是其父结点的右子结点
            System.out.println("插入情景4.2.2：插入结点是其父结点的右子结点");
            //对current进行左旋，使得insert为current的父节点
            leftRotation(newNode, currentNode);
            //把P设置为插入结点，得到情景4.2.1
            linkNode(newNode, currentNode);
            return;
        }
        //插入情景4.3：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的右子结点
        System.out.println("插入情景4.3：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的右子结点");
        // 插入情景4.3.1：插入结点是其父结点的右子结点
        if (!addLeft) {
            System.out.println("插入情景4.3.1：插入结点是其父结点的右子结点");
            //变色
            currentNode.red = false;
            parentNode.red = true;
            leftRotation(currentNode, parentNode);
            return;
        }
        //插入情景4.3.2：插入结点是其父结点的左子结点
        System.out.println("插入情景4.3.2：插入结点是其父结点的左子结点");
        linkNode(newNode, currentNode);
    }

    private void leftRotation(Node currentNode, Node parentNode) {
        // current节点为parent节点的右子节点，对parent节点进行左旋
        Node currentLeft = currentNode.left;
        currentNode.parent = parentNode.parent;
        currentNode.left = parentNode;
        if (null != parentNode.parent) {
            parentNode.parent.right = currentNode;
        }
        parentNode.parent = currentNode;
        parentNode.right = currentLeft;
        if (null != currentLeft)
            parentNode.right = currentLeft;
    }

    private void rightRotation(Node currentNode, Node parentNode) {
        // current节点为parent节点的左子节点，对parent节点进行右旋
        Node currentRight = currentNode.right;
        currentNode.right = parentNode;
        currentNode.parent = parentNode.parent;
        if (null != parentNode.parent) {
            parentNode.parent.right = currentNode;
        }
        parentNode.parent = currentNode;
        parentNode.left = currentRight;
        if (null != currentRight)
            parentNode.left = currentRight;
    }

    private void preOrder(Node node) {
        // 使用前序遍历node节点
        if (null == node) {
            return;
        }
        System.out.printf("Node(value = %s,red = %s)%n", node.value, node.red);
        preOrder(node.left);
        preOrder(node.right);
    }

    private Node findRootNode(Node currentNode) {
        //从某个节点向上，获取根节点
        return (null == currentNode.parent) ? currentNode : findRootNode(currentNode.parent);
    }

    public static void main(String[] args) {
        MyRedBlackTree myRedBlackTree = new MyRedBlackTree();
        Node root = myRedBlackTree.addNode(null, new Node(1));
        for (int i = 2; i <= 22; i++) {
            root = myRedBlackTree.addNode(root, new Node(i));
            root = myRedBlackTree.findRootNode(root);
            myRedBlackTree.preOrder(root);
            System.out.println();
            System.out.println("==========");
        }

//        Node root2 = myRedBlackTree.addNode(null, new Node(22));
//        for (int i = 21; i >= 1; i--) {
//            root2 = myRedBlackTree.addNode(root2, new Node(i));
//            root2 = myRedBlackTree.findRootNode(root2);
//            myRedBlackTree.preOrder(root2);
//            System.out.println();
//            System.out.println("==========");
//        }
    }
}
